The present invention relates to permutation logic for changing words with uncorrectable errors (UE's) into memory words that can be corrected by the error correcting code protecting the data in the memory.
In co-pending Bossen et al patent application No. 362,925 filed Mar. 29, 1982 now matured into U.S. Pat. No. 4,461,001 issued July 17, 1984 and entitled "Deterministic Permutation Algorithm", a memory address register accesses a memory word by supplying the same logical address to decoders for all bit positions of the word. However, as a result of modification by logic circuitry the address actually applied to the decoder of any particular bit position can differ from the logical address supplied by the address register. The logic circuitry is called permutation logic. Because of the permutation logic, a memory word can contain storage cells located at a number of different physical addresses that are not the logical address supplied by the memory register.
The permutation logic of the Bossen et al patent application performs a single Exclusive OR function on each of the n inputs to the decoder of the particular bit position. Each of the n digits of the word address is Exclusive ORed with a different bit to permute the address.
If the bit decoder is a two bit decoder, the mentioned permutation logic can provide to the decoder 2.sup.n or four different combinations or sequences of bit inputs. These are shown in Table 1.
TABLE 1 ______________________________________ Input Permutation Bits Bits Z1 Z0 C1,C0 00 01 10 11 ______________________________________ 00 00 01 10 11 01 01 00 11 10 10 10 11 00 01 11 11 10 01 00 ______________________________________
These four sequences form only a small subset of the possible decoder input sequences. There are actually 2.sup.n ! or 24 possible input sequences for a two bit decoder. The decimal equivalents of all possible sequences are shown in Table 2.
TABLE 2 __________________________________________________________________________ Decoder Inputs Bits Possible Input Sequences C1 C0 C1' C0' __________________________________________________________________________ 0 0 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 0 1 1 3 2 2 3 1 0 3 2 2 3 0 1 3 0 0 3 1 1 0 2 2 0 1 1 0 2 1 3 1 2 3 2 0 3 0 2 3 0 1 3 1 0 3 2 1 0 1 2 0 1 1 3 2 1 3 1 2 3 2 0 3 0 2 3 0 1 3 1 0 0 2 1 0 1 2 __________________________________________________________________________
It turns out that certain UE conditions cannot be satisfactorily resolved using any of the 2.sup.n input sequences in Table 1 where these same UE conditions could readily be allieviated if one of the other theoretically possible n! input sequences shown in Table 2 were achievable.
Co-pending Bond patent application No. 381,266 filed May 24, 1982 and entitled "Fault Alignment Control System and Circuits" now matured into U.S. Pat. No. 4,489,403 issued Dec. 18, 1984 discloses logic capable of providing more than the 2.sup.n input combinations listed in Table 1. However, the disclosed permutation devices are not "linear". Unlike the permutation devices in the referenced Bossen et al patent application, the value of permutation bits needed to access a known actual address with a given logical address cannot be calculated. Instead a table lookup scheme has to be employed to obtain the permutation bits that are necessary to transpose a logical address into an actual address. Furthermore, when expanded beyond two address bits the translation of one address in one group of four addresses will be reflected in all other groups of four addresses.
An F. J. Aichelmann, Jr. et al patent application No. 429,644, filed Sept. 30, 1982 and entitled "Memory Address Permutation Apparatus" discloses a single permutation apparatus which transposes a single logical address into a different actual address for any number of the bit positions of an accessed memory and this selection scheme allows translation word lines without affecting data in other pairs of word lines but the actual addresses are selected sequentially and the selection scheme is not linear.